package leetcode_2501_2600;

import java.util.Arrays;

public class LeeCode_2563 {
    public static void main(String[] args) {
        System.out.println(countFairPairs(new int[]{0, 1, 7, 4, 4, 5}, 3, 6));
        System.out.println(countFairPairs(new int[]{1,7,9,2,5}, 11, 11));
    }
    private static long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        int l = 0, n = nums.length;
        long ans = 0;
        while (l < n){
            int left = nums[l];
            int small = lower - left;
            int si = bigger(nums, small);
            int big = upper - left;
            int bi = smaller(nums, big);
            if(si == -1 || bi == -1){
                l++;
                continue;
            }
            ans += bi - si + 1 + (l >= si && l <= bi ? -1 : 0);
            l++;
        }
        return ans / 2;
    }
    private static int smaller(int[] arr, int goal){
        int l = 0, r = arr.length - 1;
        while (l < r){
            int m = (l + r + 1) >>> 1;
            if (arr[m] > goal){
                r = m - 1;
            }else {
                l = m;
            }
        }
        if(arr[l] > goal){
            return -1;
        }
        return l;
    }
    private static int bigger(int[] arr, int goal){
        int l = 0, r = arr.length - 1;
        while (l < r){
            int m = (l + r) >>> 1;
            if (arr[m] < goal){
                l = m + 1;
            }else {
                r = m;
            }
        }
        if(arr[l] < goal){
            return -1;
        }
        return l;
    }
}
